home *** CD-ROM | disk | FTP | other *** search
/ Inter.Net 55-1 / Inter.Net 55-1.iso / CBuilder / Setup / BCB / data.z / list.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1998-02-09  |  10.5 KB  |  359 lines
  1. #ifndef __LIST_CC
  2. #define __LIST_CC
  3. #pragma option push -b -a4 -Vx- -Ve- -w-inl -w-aus -w-sig
  4.  
  5. /***************************************************************************
  6.  *
  7.  * list.cc - Non-nline list definitions for the Standard Library
  8.  *
  9.  * $Id: list.cc,v 1.4 1996/08/28 18:42:09 smithey Exp $
  10.  *
  11.  ***************************************************************************
  12.  *
  13.  * Copyright (c) 1994
  14.  * Hewlett-Packard Company
  15.  *
  16.  * Permission to use, copy, modify, distribute and sell this software
  17.  * and its documentation for any purpose is hereby granted without fee,
  18.  * provided that the above copyright notice appear in all copies and
  19.  * that both that copyright notice and this permission notice appear
  20.  * in supporting documentation.  Hewlett-Packard Company makes no
  21.  * representations about the suitability of this software for any
  22.  * purpose.  It is provided "as is" without express or implied warranty.
  23.  *
  24.  *
  25.  ***************************************************************************
  26.  *
  27.  * (c) Copyright 1994, 1995 Rogue Wave Software, Inc.
  28.  * ALL RIGHTS RESERVED *
  29.  * The software and information contained herein are proprietary to, and
  30.  * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
  31.  * intends to preserve as trade secrets such software and information.
  32.  * This software is furnished pursuant to a written license agreement and
  33.  * may be used, copied, transmitted, and stored only in accordance with
  34.  * the terms of such license and with the inclusion of the above copyright
  35.  * notice.  This software and information or any other copies thereof may
  36.  * not be provided or otherwise made available to any other person.
  37.  *
  38.  * Notwithstanding any other lease or license that may pertain to, or
  39.  * accompany the delivery of, this computer software and information, the
  40.  * rights of the Government regarding its use, reproduction and disclosure
  41.  * are as set forth in Section 52.227-19 of the FARS Computer
  42.  * Software-Restricted Rights clause.
  43.  *
  44.  * Use, duplication, or disclosure by the Government is subject to
  45.  * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
  46.  * Technical Data and Computer Software clause at DFARS 252.227-7013.
  47.  * Contractor/Manufacturer is Rogue Wave Software, Inc.,
  48.  * P.O. Box 2328, Corvallis, Oregon 97339.
  49.  *
  50.  * This computer software and information is distributed with "restricted
  51.  * rights."  Use, duplication or disclosure is subject to restrictions as
  52.  * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
  53.  * Computer Software-Restricted Rights (April 1985)."  If the Clause at
  54.  * 18-52.227-74 "Rights in Data General" is specified in the contract,
  55.  * then the "Alternate III" clause applies.
  56.  *
  57.  **************************************************************************/
  58.  
  59. #include <stdcomp.h>
  60. #include <limits>
  61.  
  62. #define _RWSTD_LIST_SORT_COUNTERS 64
  63.  
  64. #ifndef _RWSTD_NO_NAMESPACE
  65. namespace std {
  66. #endif
  67.  
  68. template <class T, class Allocator>
  69. void list<T,Allocator>::deallocate_buffers ()
  70. {
  71.     while (buffer_list)
  72.     {
  73.         buffer_pointer tmp = buffer_list;
  74.         buffer_list = (buffer_pointer)(buffer_list->next_buffer);
  75.         list_node_alloc_type(the_allocator).deallocate(tmp->buffer,tmp->size);
  76.         buffer_alloc_type(the_allocator).deallocate(tmp,1);
  77.     }
  78.     free_list = 0;
  79.     next_avail = 0;
  80.     last = 0;
  81. }
  82.  
  83. //
  84. // This requires that T have a default constructor.
  85. //
  86.  
  87. template <class T, class Allocator>
  88. void list<T,Allocator>::resize (size_type new_size)
  89. {
  90.     T value;
  91.     if (new_size > size())
  92.         insert(end(), new_size - size(), value);
  93.     else if (new_size < size())
  94.     {
  95.         iterator tmp = begin();
  96.         advance(tmp, (difference_type) new_size);
  97.         erase(tmp, end());
  98.     }
  99. }
  100.  
  101. template <class T, class Allocator>
  102. void list<T,Allocator>::resize (size_type new_size, T value)
  103. {
  104.     if (new_size > size())
  105.         insert(end(), new_size - size(), value);
  106.     else if (new_size < size())
  107.     {
  108.         iterator tmp = begin();
  109.         advance(tmp, (difference_type) new_size);
  110.         erase(tmp, end());
  111.     }
  112. }
  113.  
  114. #ifndef _RWSTD_NO_MEMBER_TEMPLATES
  115. template <class T, class Allocator>   
  116. template<class InputIterator>
  117. void list<T,Allocator>::insert (iterator position, InputIterator first,
  118.                       InputIterator locallast)
  119. {
  120.       while (first != locallast) insert(position, *first++);
  121. }
  122. #else
  123. template <class T, class Allocator>   
  124. void list<T, Allocator>::insert (list<T, Allocator>::iterator position, 
  125.                        list<T, Allocator>::const_iterator first,
  126.                        list<T, Allocator>::const_iterator locallast)
  127. {
  128.     while (first != locallast) insert(position, *first++);
  129. }
  130. template <class T, class Allocator>
  131. void list<T, Allocator>::insert (list<T, Allocator>::iterator position, 
  132.                                  const T* first, const T* locallast)
  133. {
  134.     while (first != locallast) insert(position, *first++);
  135. }
  136. #endif
  137.  
  138. template <class T, class Allocator>
  139. void list<T, Allocator>::insert_aux (list<T, Allocator>::iterator position, 
  140.                                  size_type n, const T& x)
  141. {
  142.     while (n--) insert(position, x);
  143. }
  144.  
  145. template <class T, class Allocator>
  146. _TYPENAME list<T, Allocator>::iterator 
  147. list<T, Allocator>::erase (list<T, Allocator>::iterator first, 
  148.                            list<T, Allocator>::iterator locallast)
  149. {
  150.     iterator tmp = end();
  151.     while (first != locallast) 
  152.     {
  153.       tmp = erase(first++);
  154.     }
  155.     return tmp;
  156. }
  157.  
  158. template <class T, class Allocator>
  159. list<T, Allocator>& list<T, Allocator>::operator= (const list<T, Allocator>& x)
  160. {
  161.     if (this != &x)
  162.     {
  163.         iterator first1 = begin();
  164.         iterator last1 = end();
  165.         const_iterator first2 = x.begin();
  166.         const_iterator last2 = x.end();
  167.         while (first1 != last1 && first2 != last2) *first1++ = *first2++;
  168.         if (first2 == last2)
  169.             erase(first1, last1);
  170.         else
  171.             insert(last1, first2, last2);
  172.     }
  173.     return *this;
  174. }
  175.  
  176. template <class T, class Allocator>
  177. void list<T, Allocator>::remove (const T& value)
  178. {
  179.     iterator first = begin();
  180.     iterator last = end();
  181.     while (first != last)
  182.     {
  183.         iterator next = first;
  184.         ++next;
  185.         if (*first == value) erase(first);
  186.         first = next;
  187.     }
  188. }
  189.  
  190. template <class T, class Allocator>
  191. void list<T, Allocator>::unique ()
  192. {
  193.     iterator first = begin();
  194.     iterator last = end();
  195.     if (first == last) return;
  196.     iterator next = first;
  197.     while (++next != last)
  198.     {
  199.         if (*first == *next)
  200.             erase(next);
  201.         else
  202.             first = next;
  203.         next = first;
  204.     }
  205. }
  206.  
  207. template <class T, class Allocator>
  208. void list<T, Allocator>::merge (list<T, Allocator>& x)
  209. {
  210.     iterator first1 = begin();
  211.     iterator last1 = end();
  212.     iterator first2 = x.begin();
  213.     iterator last2 = x.end();
  214.     while (first1 != last1 && first2 != last2)
  215.     {
  216.         if (*first2 < *first1)
  217.         {
  218.             iterator next = first2;
  219.             transfer(first1, first2, ++next, x);
  220.             first2 = next;
  221.         }
  222.         else
  223.             first1++;
  224.     }
  225.     if (first2 != last2) 
  226.         transfer(last1, first2, last2, x);
  227. }
  228.  
  229. template <class T, class Allocator>
  230. void list<T, Allocator>::reverse ()
  231. {
  232.     if (size() < 2) return;
  233.     for (iterator first = ++begin(); first != end();)
  234.     {
  235.         iterator old = first++;
  236.         transfer(begin(), old, first, *this);
  237.     }
  238. }    
  239.  
  240.  
  241. template <class T, class Allocator>
  242. void list<T, Allocator>::sort ()
  243. {
  244.     if (size() < 2) return;
  245.  
  246.     list<T, Allocator> carry(get_allocator());
  247.     list<T, Allocator> counter[_RWSTD_LIST_SORT_COUNTERS];
  248.     for (int i = 0; i < _RWSTD_LIST_SORT_COUNTERS; i++)
  249.       counter[i].set_allocator(get_allocator());
  250.  
  251.     int fill = 0;
  252.     while (!empty())
  253.     {
  254.         carry.splice(carry.begin(), *this, begin());
  255.  
  256.         int i = 0;
  257.         while (i < fill && !counter[i].empty())
  258.         {
  259.             counter[i].merge(carry);
  260.             carry.swap(counter[i++]);
  261.         }
  262.         carry.swap(counter[i]);         
  263.         if (i == fill) ++fill;
  264.     } 
  265.     while (fill--) 
  266.     {  
  267.       merge(counter[fill]);
  268.     }
  269. }
  270.  
  271. #ifndef _RWSTD_NO_MEMBER_TEMPLATES
  272. template<class T, class Allocator>
  273. template<class Predicate> void list<T, Allocator>::remove_if (Predicate pred)
  274. {
  275.     iterator first = begin();
  276.     iterator last = end();
  277.     while (first != last)
  278.     {
  279.         iterator next = first;
  280.         ++next;
  281.         if (pred(*first)) erase(first);
  282.         first = next;
  283.     }
  284. }
  285.  
  286. template<class T, class Allocator>
  287. template<class BinaryPredicate> void list<T, Allocator>::unique (BinaryPredicate pred)
  288. {
  289.     iterator first = begin();
  290.     iterator last = end();
  291.     if (first == last) return;
  292.     iterator next = first;
  293.     while (++next != last)
  294.     {
  295.         if (pred(*first, *next))
  296.             erase(next);
  297.         else
  298.             first = next;
  299.         next = first;
  300.     }
  301. }
  302.  
  303. template<class T, class Allocator>
  304. template<class Compare> void list<T, Allocator>::merge (list<T, Allocator>& x, Compare comp)
  305. {
  306.     iterator first1 = begin();
  307.     iterator last1  = end();
  308.     iterator first2 = x.begin();
  309.     iterator last2  = x.end();
  310.     while (first1 != last1 && first2 != last2)
  311.     {
  312.         if (comp(*first2, *first1))
  313.         {
  314.             iterator next = first2;
  315.             transfer(first1, first2, ++next, x);
  316.             first2 = next;
  317.         }
  318.         else
  319.             first1++;
  320.     }
  321.     if (first2 != last2) 
  322.         transfer(last1, first2, last2, x);
  323. }
  324.  
  325. template<class T, class Allocator>
  326. template<class Compare> void list<T, Allocator>::sort (Compare comp)
  327. {
  328.     if (size() < 2) return;
  329.  
  330.     list<T, Allocator> carry(get_allocator());
  331.     list<T, Allocator> counter[ _RWSTD_LIST_SORT_COUNTERS];
  332.     for (int i = 0; i < _RWSTD_LIST_SORT_COUNTERS; i++)
  333.       counter[i].set_allocator(get_allocator());
  334.     int fill = 0;
  335.     while (!empty())
  336.     {
  337.         carry.splice(carry.begin(), *this, begin());
  338.         int i = 0;
  339.         while (i < fill && !counter[i].empty())
  340.         {
  341.             counter[i].merge(carry, comp);
  342.             carry.swap(counter[i++]);
  343.         }
  344.         carry.swap(counter[i]);         
  345.         if (i == fill) ++fill;
  346.     } 
  347.     while (fill--) merge(counter[fill]);
  348. }
  349. #endif /*_RWSTD_NO_MEMBER_TEMPLATES*/
  350.  
  351. #undef _RWSTD_LIST_SORT_COUNTERS
  352.  
  353. #ifndef _RWSTD_NO_NAMESPACE
  354. }
  355. #endif
  356.  
  357. #pragma option pop
  358. #endif /* __LIST_CC */
  359.